1. Field of the Invention
The present invention relates to a circuit analysis device for analyzing delay time for a digital circuit including a wiring that bundles multiple bits, a circuit analysis method thereof and a program for causing a computer to execute the method.
2. Description of the Related Art
As semiconductor process technology progresses, the design scale of digital circuits is becoming larger and complexity of digital circuits is increasing year after year. There is also increasingly stronger demand for a technology that will ensure at the initial design stage that, taking into consideration the design scale and complexity of the circuit, the digital circuit will operate correctly after manufacturing. As for a synchronous digital circuit which is currently in the mainstream, processing is performed while synchronizing the circuit by means of a periodic pulse signal called a clock. Therefore, it is necessary to always finish a unit operation of the circuit in a time period equivalent to one clock period. To assure that a designed circuit correctly operates after manufacturing, there is a generally used technique called Static Timing Analysis (STA) for analyzing the maximum operating frequency of the circuit in a design stage.
The STA is a technique for analyzing delay time of a path in a circuit where the operation must be completed within a given time period, such as a clock period or a time period which is an integral multiple thereof. The STA can execute a delay analysis by taking less time than a delay simulation that is conventionally used. The path which requires the operation to be completed within a given time period is generally a path leading from an external input terminal to a memory unit or a path leading from the memory unit to an external output terminal in the circuit. If the reference time is the time for transmitting a signal from the origin to an end direction of the path as a subject of the delay analysis, the delay time is analyzed by estimating the signal arrival time to the components existing on the path.
An example of a conventional circuit design system is described in U.S. Pat. No. 4,263,651 (hereinafter, referred to as Document 1) and Robert B. Hitchcock Sr., “Timing Verification and the Timing Analysis Program,” Proceedings of 19th Design Automation Conference, pp. 594 to 604 (hereinafter, referred to as Document 2). FIG. 1 is a block diagram showing a configuration example of the conventional circuit design system.
As shown in FIG. 1, the conventional circuit design system includes input device 500 as input means, data processing device 510, storage device 520 and output device 530 as output means. Data processing device 510 is configured to include circuit input means 511, delay analysis means 512 and result output means 513. Hereunder, operations of the conventional circuit design system will be briefly described.
If connection information 521 indicating the relationship of the connected components of a logic circuit is inputted via input device 500, data processing device 510 transfers connection information 521 to storage device 520 to store it therein. In general, connection information 521 about the logic circuit is described by using a hardware description language or the like, where the components constituting the circuit and connection relations among components are defined. Next, if delay information 522 indicating the delay time of each of the components existing in the circuit is inputted, data processing device 510 transfers delay information 522 to storage device 520 to store it therein. Data processing device 510 calculates the longest path out of the path leading from the external input terminal to the memory unit or the path leading from the memory unit to the external output terminal in the circuit with reference to delay information 522 about each of the components. There are many proposed methods of efficiently calculating the longest path, which are disclosed in Document 1 for instance. It is thereby possible to acquire the longest signal path.
Subsequently, data processing device 510 calculates the delay of the circuit according to the STA technique. Here, the one of general operations of the STA technique will be described. The delay time of each of the components constituting the circuit is measured in advance, and is stored in storage device 520 as described above. Based on the information about the connection relations among the components of the circuits, the signal arrival time is acquired about each of the components on the path from the origin, such as the external input terminal, to the end, such as an external output terminal and a register. As for the components that receive signals from each of the multiple paths, the latest signal arrival time from the origin is employed so as to pass the employed signal arrival time to a next component. Thus, the latest arrival times of the signal at the terminals of the circuit are passed on to the following component in turn to estimate the signal arrival time at the end. In this case, it is possible to determine the signal with the latest arrival time in the entire circuit at high speed by referring to the longest signal path acquired.
The STA technique has been implemented for circuit representations of an abstract level called a gate level, where logic gates of a small number of inputs are circuit components. As for the circuits of the gate level, the wire connections among the circuit components corresponds to one physical wiring, and there is no assumption about a signal line called a bus which is a bundle of multiple signal lines of semantic coherence. The bus transmits signals of a bit count having a fixed width in parallel. In the case of the circuits of the gate level, the delay time of a circuit component is generally only determined by the circuit component, which is not dependent on what path the signal has followed to arrive at the circuit component. As for the related STA technique, it is presumed that the delay time of the path depends on the delay time of the components on the path but does not depend on the wiring configuration.
In recent years, as the circuit scale becomes larger and more complicated, circuit design is implemented at a level called an RT (Register Transfer) level which is a more abstract level than the gate level. Thus, a high-speed delay-analysis at the RT level is required. Especially, in the case of behavioral synthesis CAD (Computer Aided Design) for automatically synthesizing a circuit of the RT level with behavioral description in C named software language as the input, high-speed execution of the STA at the RT level is required because an optimal circuit must be searched for while generating and evaluating a large number of the circuits of the RT level.
As for the circuit components in the case of the RT level, circuit configuration is represented by larger-scale components called a functional unit and a selector and connections thereof in addition to basic logic devices. Even when multiple bit lines are inputted in parallel, the multiple bit lines are bundled and described as one signal line. Therefore, there are cases where multiple signal lines are physically used even though the connection of components is one connection in terms of the circuit representation. A delay estimation error may thereby be generated.
There is a chain delay effect as one of the causes of the delay estimation error in the case of the RT level. “Chain” means to mutually connect the components which input and output the signals in series for bundling the bit lines without putting the memory unit between them. The chain delay effect refers to a phenomenon in which the entire component group chained as above has a different delay time value from the value acquired by adding the delay time of separate components as to all the chained components. The chain delay effect is disclosed in Japanese Patent Laid-Open No. 11-96203 (hereinafter, referred to as Document 3) and Mukund Sivaraman, Shail Aditya, “Cycle-time Aware Architecture Synthesis of Custom Hardware Accelerators,” Proceedings of the 2002 international conference on Compilers, architecture and synthesis for embedded systems, pp. 35 to 42 (hereinafter, referred to as Document 4). Hereunder, chain delay time refers to the delay time estimated for one of the components when the chain delay effect is generated by connecting two components.
The chain delay effect will be described by using an example of a chain connection of carry-propagate adders. FIG. 2 is a diagram showing a circuit example of the chain connection according to carry-propagate adders. FIG. 2(a) shows a representation at the RT level, and FIG. 2(b) shows a circuit representation at the gate level. Hereunder, the carry-propagate adders are simply called adders.
The circuit shown in FIG. 2(a) has 4-bit adders 551 and 552 serially connected in two stages. The discrete delay time of adders 551 and 552 was 4d by measurement. The delay times of 1-bit addition gates 553, represented as one blocks in FIG. 2(b), are uniformly d. As shown in FIG. 2(b), the longest signal path of the entire circuit is the path indicated by a dotted line, and the longest delay time is 5d. In the case of implementing the STA in the circuit at the RT level, the delay time of the circuit is acquired as 4d+4d=8d because adders 551 and 552 whose delay time is 4d are connected in two stages. As is evident from this result, if the delay time is sought, based on the STA technique, as to the circuit at the RT level, it includes a significant error against 5d which is an STA result at the gate level.
As for delay information about the components in view of the chain delay effect, the delay time should be measured in advance with the components, that have the chain delay effect, connected in series with other components so as to store the delay information in storage device 520 apart from delays of the discrete components. This is reasoned by analogy with Stefaan Note, Francky Catthoor, Gert Goossens, Hugo De Man, “Combined Hardware selection and Pipelining in High Performance Data-Path Design,” IEEE Transactions on Computer-Aided Design, vol. 9, pp. 413 to 423, April 1992 (hereinafter, referred to as Document 5).
However, there are the cases where the delay cannot be correctly measured even by combining the technique reasoned by analogy in Document 5 with the above-mentioned general STA technique. It is because the chain delay effect which is generated by the connection relation of two components also occurs in the case where a different kind of component is put between the components. An example thereof will be described below.
FIG. 3 is a diagram showing an example of connecting another component between the serially connected adders in two stages. As shown in FIG. 3, multiplexer 555 is connected as another kind of component between adders 551 and 552. At the gate level, multiplexer 555 has a structure in which the components of the same logic are arranged in parallel at each bit. In the circuit at the RT level shown in FIG. 3(a), the chain delay effect exists due to the mutual connection of the adders although adders 551 and 552 are not connected in series.
The general STA technique is based on the premise that a delay of the component in a given circuit is generally independent of the path. It is possible, by referring to the component and a component connected immediately before it, to consider the chain delay effect according to the related STA technique described above. In the case where the chain delay effect exists between components not directly connected, however, the arrival time of the signal component existing on the path between the components depends on the path. Therefore, the latest path of the arrival time of the signal component cannot be determined only from the component existing on the origin side. Thus, the delay time of such a circuit cannot be correctly measured except by an inefficient method such as counting all the paths existing in the circuit.